Một thuật toán kiểm chứng V cho ngôn ngữ A là một thuật toán (tất định) sao cho

• Với mọi chuỗi x trong ngôn ngữ A, tồn tại chuỗi y sao cho V(x,y)=1.
• Với mọi chuỗi x không nằm trong A, V(x,y)=0 với mọi y.

Thời gian thực thi của V được tính theo tham số là độ dài của x.

NP được định nghĩa là tập hợp các ngôn ngữ/bài toán có thuật toán kiểm chứng chạy trong thời gian đa thức.o